package canFinish;

import javax.swing.plaf.FontUIResource;
import java.util.*;

public class Solution {
//    class Graph{
//        class Node {
//            int value;
//            List<Node> next;
//            public Node(int value) {
//                this.value = value;
//                this.next = new ArrayList<>();
//            }
//        }
//        Node[] nodes;
//        public Graph(int numCourses,int[][] prerequisites) {
//            nodes = new Node[numCourses];
//            for (int i = 0; i < numCourses; i++) {
//                nodes[i] = new Node(i);
//            }
//            for (int i = 0; i < prerequisites.length; i++) {
//                nodes[prerequisites[i][0]].next.add(nodes[prerequisites[i][1]]);
//            }
//        }
//    }
//    boolean[] canChooseCourse;
//    boolean[] used; // 表示这个点是否已经遍历过
//    public boolean canFinish(int numCourses, int[][] prerequisites) {
//        // 能否选课
//        // 初始化图
//        // 一个有向图中是否含有环
//        Graph g = new Graph(numCourses,prerequisites);
//        canChooseCourse = new boolean[numCourses];
//        used = new boolean[numCourses];
//        for (int i = 0; i < numCourses; i++) {
//
//            Stack<Integer> stack = new Stack<>();
//            if(!dfs(g,i,stack)){
//               return false;
//            }
//        }
//        return true;
//    }
//    // 遍历有向图
//    private boolean dfs(Graph g,int course,Stack<Integer> path){
//        if(path.contains(course)){
//            return false; // 有环
//        }
//        path.add(course);
//        boolean ans = true;
//        for (int i = 0; i < g.nodes[course].next.size(); i++) {
//            int c = g.nodes[course].next.get(i).value; // 选这门课程需要选这个课程
//            if(used[c]){
//                ans=ans&&canChooseCourse[c];
//                continue;
//            }
//            ans=ans&&dfs(g,c,path);
//        }
//        used[course] = true;
//        canChooseCourse[course] = ans;
//        path.pop();
//        return ans;
//    }
    List<Integer>[] graph; // graph[i]表示每个点的后驱
    int[] indegree; // 每个点的入度
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 拓扑排序
        // 拓扑排序的流程
        // 在图中选择一个无前驱的顶点（入度为0的点）并放入栈中
        // 在图中删除该节点和所有以它为尾的弧（将该点的后驱节点的入度-1）

        // 初始化图
        graph = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < prerequisites.length; i++) {
            graph[prerequisites[i][0]].add(prerequisites[i][1]);
        }
        // 得到所有点的入度
        indegree = new int[numCourses];
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[i].size(); j++) {
                indegree[graph[i].get(j)]++;
            }
        }
        // Stack<Integer>存放所有入度位为0的点
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < indegree.length; i++) {
            if(indegree[i] == 0) stack.push(i);
        }
        List<Integer> topo = new ArrayList<>(); // 记录拓扑排序已经排列好的节点
        while (!stack.isEmpty()) {
            // 找到所有入度为0的点 从图中删除它
            int course = stack.pop();
            // 删除这个点以及它的尾部弧
            for (int i = 0; i < graph[course].size(); i++) {
                indegree[graph[course].get(i)]--;
                // 把所有入度为0的点加入栈中
                if(indegree[graph[course].get(i)] == 0) stack.push(graph[course].get(i));
            }
            topo.add(course);
        }
        if(topo.size()!=numCourses){
            return new int[]{};
        }
        int[] ans = new int[topo.size()];
        for (int i = topo.size()-1; i >= 0; i--) {
            ans[topo.size()-1-i] = topo.get(i);
        }
        return ans;
    }
}
